//DAY 1

//https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
//旋转数组的最小数字
#include<vector>
#include<string>
using namespace std;

class Solution {
public:
    int minArray(vector<int>& numbers) 
    {
        int left=0;
        int right=numbers.size()-1;
        int mid=0;
        //采用二分法
        while(left<=right)
        {
            mid=(left+right)/2;
            if(numbers[mid]<numbers[right])//根据mid和right判断最小值位置
            {
                right=mid;
            }
            else if(numbers[mid]>numbers[right])
            {
                left=mid+1;
            }
            else if(numbers[mid]==numbers[right])//重复无法判断位置
            {
                right--;
            }
        }
         return numbers[left];
    }
};

//https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
//剑指 Offer 21. 调整数组顺序使奇数位于偶数前面


class Solution {
public:
    vector<int> exchange(vector<int>& nums) 
    {
        //类比快排前后指针法，采用前后指针
        int cur=0;
        int prev=-1;
        while((int)prev<(int)(nums.size()-1))
        {
            if(nums[cur]%2==1)
            {
                if(nums[prev+1]%2==1)
                {
                    prev++;
                    swap(nums[cur],nums[prev]);
                }
            }
            else
            {
                while(prev+1<nums.size()&&nums[prev+1]%2==0)
                {
                    prev++;
                }
                if(prev+1>=nums.size())
                {
                    break;
                }
                prev++;
                swap(nums[cur],nums[prev]);
            }
            cur++;
        }
        return nums;
    }
};




//剑指 Offer 39. 数组中出现次数超过一半的数字
// https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/

class Solution {
public:
    int majorityElement(vector<int>& nums) 
    {
        int tmp=nums[0];
        int count=1;
        for(int i=1;i<nums.size();i++)
        {
            if(count==0)
            {
                tmp=nums[i];
            }
            if(tmp==nums[i])
            {
                count++;
            }
            else
            {
                count--;
            }
        }
        return tmp;
    }
};


// DAY 2
// 剑指 Offer 05. 替换空格
// https://leetcode.cn/problems/ti-huan-kong-ge-lcof/

class Solution {
public:
    string replaceSpace(string s) 
    {
        //时间复杂度为O(n)
        //先将字符串扩充，使用双指针
        int count=0;
        for(auto ch:s)
        {
            if(ch==' ')
            {
                count+=2;
            }
        }
        int new_=s.size()+count-1;
        int old_=s.size()-1;
        s.resize(s.size()+count);
        while(old_>=0)
        {
            if(s[old_]!=' ')
            {
                s[new_]=s[old_];
                new_--;
                old_--;
            }
            else
            {
                s[new_]='0';
                s[new_-1]='2';
                s[new_-2]='%';
                new_-=3;
                old_--;
            }
        }
        return s;


    }

};

// 剑指 Offer 07. 重建二叉树
// https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/

// Definition for a binary tree node.
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:

    TreeNode* build_tree(vector<int>& preorder,vector<int>&inorder,
                        int pbegin,int pend,int ibegin,int iend)
    {
        if(pbegin>pend&&ibegin>iend)
        {
            return nullptr;
        }
        int val_loc=ibegin;
        //cout<<preorder[pbegin]<<endl;
        while(inorder[val_loc]!=preorder[pbegin])
        {
            val_loc++;
        }
        int il_left=ibegin;
        int il_right=val_loc-1;
        int ir_left=val_loc+1;
        int ir_right=iend;
        int pl_left=pbegin+1;
        int pl_right=pbegin+1+(il_right-il_left);
        int pr_left=pend-(ir_right-ir_left);
        int pr_right=pend;
        //cout<<il_left<<" "<<il_right<<" "<<pl_left<<" "<<pl_right<<endl;
        //cout<<ir_left<<" "<<ir_right<<" "<<pr_left<<" "<<pr_right<<endl;
        //cout<<preorder[pbegin]<<endl;
        TreeNode* root=new TreeNode(preorder[pbegin]);
        root->left=build_tree(preorder,inorder,pl_left,pl_right,il_left,il_right);
        root->right=build_tree(preorder,inorder,pr_left,pr_right,ir_left,ir_right);
        return root;

    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        TreeNode* root = build_tree(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
        return root;
    }
};

// 剑指 Offer 06. 从尾到头打印链表
// https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

// Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:

    void reverse_(vector<int>& ans, ListNode* cur)
    {
        if(cur==nullptr)
        {
            return;
        }
        reverse_(ans,cur->next);
        ans.push_back(cur->val);

    }
    vector<int> reversePrint(ListNode* head) 
    {
        vector<int> ans;
        reverse_(ans,head);
        return ans;
    }
};
